public class BTree {
    private final int M;
    private int size = 0;
    public BTreeNode root;
    class BTreeNode{
        int[] val;
        BTreeNode[] child;
        BTreeNode parent;
        int size;

        public BTreeNode() {
            this.val = new int[M];
            this.child = new BTreeNode[M+1];
        }
    }
    public BTree(int m) {
        this.M = m;
    }

    //插入
    public boolean insert(int a) {
        if (this.size == 0) {
            root = new BTreeNode();
            root.size++;
            this.size++;
            root.val[0] = a;
            return true;
        }
        //树不为空
        //找到待插入位置
        BTreeNode node = find(a);
        if (node == null) {
            return false;
        }
        //插入值
        if (!nodeAddVal(node, a)) {
            throw new RuntimeException("B树中插入数值失败");
        }
        //判断是否需要分裂
        while (node != null && node.size == M) {
            split(node);
            node = node.parent;
        }
        return true;
    }

    //在节点中添加值
    private boolean nodeAddVal(BTreeNode node, int a) {
        if (node == null) {
            return false;
        }
        for (int i = node.size-1; i >= 0; i--) {
            if (node.val[i] > a) {
                node.val[i+1] = node.val[i];
            } else {
                node.val[i+1] = a;
                node.size++;
                return true;
            }
        }
        node.val[0] = a;
        node.size++;
        return true;
    }

    //分裂
    private void split(BTreeNode node) {

        BTreeNode newNode = new BTreeNode();

        for (int i = node.size/2 + 1, j = 0; i < node.size; i++, j++) {
            newNode.val[j] = node.val[i];
            newNode.size++;
            newNode.child[j] = node.child[i];
            node.val[i] = 0;
            node.child[i] = null;
            if (newNode.child[j] != null) {
                newNode.child[j].parent = newNode;
            }
        }
        newNode.child[newNode.size] = node.child[node.size];
        if (newNode.child[newNode.size] != null) {
            newNode.child[newNode.size].parent = newNode;
        }
        node.child[node.size] = null;
        node.size = node.size/2;

        if (node == root) {
            //根节点分裂
            BTreeNode newRoot = new BTreeNode();
            newRoot.val[0] = node.val[node.size];
            node.val[node.size] = 0;
            newRoot.child[0] = node;
            newRoot.child[1] = newNode;
            newRoot.size++;
            this.root = newRoot;
            node.parent = this.root;
            newNode.parent = this.root;
            this.size += 2;
            return;
        }
        //非根节点
        newNode.parent = node.parent;
        int a = node.val[node.size];
        node.val[node.size] = 0;
        for (int i = node.parent.size-1; i >= 0; i--) {
            if (node.parent.val[i] > a) {
                node.parent.val[i+1] = node.parent.val[i];
                node.parent.child[i+2] = node.parent.child[i+1];
            } else {
                node.parent.val[i+1] = a;
                node.parent.child[i+2] = newNode;
                node.parent.size++;
                this.size++;
                return;
            }
        }

        node.parent.val[0] = a;
        node.parent.child[1] = newNode;
        node.parent.size++;
        this.size++;
    }

    //找到待插入位置
    private BTreeNode find(int val) {
        if (root == null) {
            return null;
        }
        BTreeNode tmp = root;
        BTreeNode ret = null;
        while (tmp != null) {
            ret = tmp;
            for (int i = 0; i < tmp.size; i++) {
                if (val < tmp.val[i]) {
                    tmp = tmp.child[i];
                    break;
                }
                if (val == tmp.val[i]) {
                    return null;
                }
                if (i == tmp.size-1) {
                    tmp = tmp.child[i+1];
                    break;
                }
            }
        }

        return ret;
    }
}
